package com.wcj.tree.recursion;

import com.wcj.tree.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
 */
public class 对称二叉树 {

    /**
     * 递归
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        return check(root,root);
    }

    private boolean check(TreeNode root, TreeNode root1) {
        if (root == null && root1 == null){
            return true;
        }
        if (root == null || root1 == null){
            return false;
        }
        return root.val == root1.val &&
                check(root.left, root1.right) &&
                check(root.right,root1.left);
    }

    /**
     * 迭代
     * @param root
     * @return
     */
    public boolean isSymmetric2(TreeNode root) {
        return check2(root,root);
    }

    private boolean check2(TreeNode root, TreeNode root1) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        queue.offer(root1);

        while (!queue.isEmpty()) {
            root = queue.poll();
            root1 = queue.poll();
            if (root == null && root1 == null){
                continue;
            }
            if ((root == null || root1 == null) || (root.val != root1.val)){
                return false;
            }
            queue.offer(root.right);
            queue.offer(root1.left);
            queue.offer(root.left);
            queue.offer(root1.right);
        }
        return true;
    }





















}
